<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      // NO.1 从英文中重建数字

      // 给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。
      // 温馨提示：0的英文是zero，1的英文是one，2的英文是two，3的英文是three，4的英文是four，5的英文是five，6的英文是six，7的英文是seven，8的英文是eight，9的英文是nine。
      // 示例 1：
      // 输入：s = "owoztneoer"
      // 输出："012"

      // 示例 2：
      // 输入：s = "fviefuro"
      // 输出："45"

      // 思路：首先我们可以统计每个字母分别在哪些数字中出现：
      //  可以发现z, w, u, x, g 都只在一个数字中，即 0, 2, 4, 6, 8 中出现。因此我们可以使用一个哈希表统计每个字母出现的次数，那么 z, w, u, x, g 出现的次数，即分别为 0, 2, 4, 6, 8出现的次数。

      // 随后我们可以注意那些只在两个数字中出现的字符：

      //h 只在 3,8 中出现。由于我们已经知道了 8 出现的次数，因此可以计算出 3 出现的次数。

      //f 只在 4,5 中出现。由于我们已经知道了 4 出现的次数，因此可以计算出 5 出现的次数。

      //s 只在 6,7 中出现。由于我们已经知道了 6 出现的次数，因此可以计算出 7 出现的次数。

      // 此时，我们还剩下 1 和 9 的出现次数没有求出：

      // o 只在 0, 1, 2, 4 中出现，由于我们已经知道了 0, 2, 4出现的次数，因此可以计算出 1 出现的次数。
      // 最后的 9 就可以通过n, i, e 中的任一字符计算得到了。这里推荐使用i 进行计算，因为n 在 9 中出现了 2 次，e 在 3 中出现了 2 次，容易在计算中遗漏。

      // 当我们统计完每个数字出现的次数后，我们按照升序将它们进行拼接即可。

      // var originalDigits = function (s) {
      //   const c = new Map()
      //   for (const e of s) {
      //     //  map对象统计每个字符出现的次数，第一次出现默认0+1，再次出现就是原值再加1
      //     // c.set(e, (c.get(e) || 0) + 1)
      //     if (c[e]) {
      //       c[e]++
      //     } else {
      //       c[e] = 1
      //     }
      //   }
      //   const res = []
      //   // z, w, u, x, g 都只在一个数字中，即 0, 2, 4, 6, 8
      //   while (c['z']) {
      //     res.push(0)
      //     // 存在就减去原来map对象中的值
      //     c['z']--
      //     c['e']--
      //     c['r']--
      //     c['o']--
      //   }
      //   while (c['w']) {
      //     res.push(2)
      //     // 存在就减去原来map对象中的值
      //     c['t']--
      //     c['w']--
      //     c['o']--
      //   }
      //   while (c['u']) {
      //     res.push(4)
      //     c['f']--
      //     c['o']--
      //     c['u']--
      //     c['r']--
      //   }
      //   while (c['x']) {
      //     res.push(6)
      //     c['s']--
      //     c['i']--
      //     c['x']--
      //   }
      //   while (c['g']) {
      //     res.push(8)
      //     c['e']--
      //     c['i']--
      //     c['g']--
      //     c['h']--
      //     c['t']--
      //   }
      //   while (c['h']) {
      //     res.push(3)
      //     c['t']--
      //     c['h']--
      //     c['r']--
      //     c['e']--
      //     c['e']--
      //   }
      //   while (c['f']) {
      //     res.push(5)
      //     c['f']--
      //     c['i']--
      //     c['v']--
      //     c['e']--
      //   }
      //   while (c['s']) {
      //     res.push(7)
      //     c['s']--
      //     c['e']--
      //     c['v']--
      //     c['e']--
      //     c['n']--
      //   }
      //   while (c['o']) {
      //     res.push(1)
      //     c['o']--
      //     c['n']--
      //     c['e']--
      //   }
      //   while (c['i']) {
      //     res.push(9)
      //     c['n']--
      //     c['i']--
      //     c['n']--
      //     c['e']--
      //   }
      //   return res.sort().join('')
      // }
      // console.log(originalDigits('owoztneoer'), '11')
      // ****************************** *************************************************************************************************************************
      //NO.2两数相加
      //给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
      //请你将两个数相加，并以相同形式返回一个表示和的链表。
      // 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
      // 示例 1：
      // 输入：l1 = [2,4,3], l2 = [5,6,4]
      // 输出：[7,0,8]
      // 解释：342 + 465 = 807.

      // 示例 2：
      // 输入：l1 = [0], l2 = [0]
      // 输出：[0]

      // 示例 3：
      // 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
      // 输出：[8,9,9,9,0,0,0,1]

      // 思路: 参数l1 l2 和输出结果类型为ListNode 不是简单数组。链表结构
      // let listNode = {
      //   val: 1,
      //   next: {
      //     val: 2,
      //     next: {
      //       val: 3,
      //       next: {},
      //     },
      //   },
      // }
      /**
       * @param {ListNode} l1
       * @param {ListNode} l2
       * @return {ListNode}
       */

      //1.首先取出“+”左右两边两个数的最低位，也就是
      // let val1 = l1.val
      // let val2 = l2.val

      //2.其次求出他们的和并作为输出结果的最低位（由于输出的结果是链表的形式保存，所以我们应该写成这种形式）
      // let sum = new ListNode('0')
      // sum.next = new ListNode(“结果” % 10)//之所以要“结果” % 10是因为我们的计算结果是有可能大于10的，所以需要取余

      // 定义链表
      // function ListNode(val, next) {
      //   this.val = val === undefined ? 0 : val
      //   this.next = next === undefined ? null : next
      // }
      // // 定义输入
      // let l1 = {
      //   val: 2,
      //   next: {
      //     val: 4,
      //     next: {
      //       val: 3,
      //       next: null,
      //     },
      //   },
      // }
      // let l2 = {
      //   val: 5,
      //   next: {
      //     val: 6,
      //     next: {
      //       val: 4,
      //       next: null,
      //     },
      //   },
      // }
      // var addTwoNumbers = function (l1, l2) {
      //   // 1.首先定义一个头部链表
      //   let head = new ListNode(0)
      //   // 如果直接返回 head的话得到的是循环最后的一次结果，所以需要开始的时候浅拷贝一个变量放置
      //   let result = head
      //   let ten = 0 // 十位制标识+1处理
      //   // 必须判断ten成立
      //   while (ten || l1 || l2) {
      //     let val1 = l1 == null ? 0 : l1.val // 有的链表长度不一，可能后面没有值，此时需要设置默认值为0
      //     let val2 = l2 == null ? 0 : l2.val
      //     let sum = val1 + val2 + ten // 两个数相加 如果之前一位是十进制过来的话此时的ten 会是1 如果不是十进制过来的此时还是0 不影响
      //     // 这里判断2个数之和是否大于10 给ten标识赋值
      //     ten = sum > 9 ? 1 : 0
      //     head.next = new ListNode(sum % 10)
      //     head = head.next
      //     if (l1) {
      //       l1 = l1.next
      //     }
      //     if (l2) {
      //       l2 = l2.next
      //     }
      //   }
      //   return result.next
      // }
      // console.log(addTwoNumbers(l1, l2))

      // ****************************** *************************************************************************************************************************
      // NO.3 无重复字符的最长子串
      // 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

      // 示例 1:
      // 输入: s = "abcabcbb"
      // 输出: 3
      // 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
      // 示例 2:
      // 输入: s = "bbbbb"
      // 输出: 1
      // 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

      // 示例 3:
      // 输入: s = "pwwkew"
      // 输出: 3
      // 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
      //      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

      // 示例 4:
      // 输入: s = ""
      // 输出: 0
      // 思路：滚轮从开头依次往后，比较，如果遇到相同的，则删除之前所有元素，重新计量。

      // var lengthOfLongestSubstring = function (s) {
      //   let result = 0
      //   let arr = []
      //   for (let i = 0; i < s.length; i++) {
      //     if (arr.indexOf(s[i]) !== -1) {
      //       console.log(arr.indexOf(s[i]), 'ar')
      //       arr.splice(0, arr.indexOf(s[i]) + 1)
      //     }
      //     arr.push(s[i])
      //     result = Math.max(result, arr.length)
      //   }
      //   return result
      // }

      // ****************************** *************************************************************************************************************************
      // NO.4 最长回文子串
      // 给你一个字符串 s，找到 s 中最长的回文子串。

      // 示例 1：
      // 输入：s = "babad"
      // 输出："bab"
      // 解释："aba" 同样是符合题意的答案。

      // 示例 2：
      // 输入：s = "cbbd"
      // 输出："bb"

      // 示例 3：
      // 输入：s = "a"
      // 输出："a"

      // 示例 4：
      // 输入：s = "ac"
      // 输出："a"
      // 垃圾写法，内存消耗过大：
      // var longestPalindrome = function (s) {
      //   if (s.length == 1) {
      //     return s
      //   }
      //   let arr = []
      //   let temp = []
      //   for (let i in s) {
      //     arr.push(s[i])
      //   }
      //   for (let i = 0; i < arr.length; i++) {
      //     for (let j = i; j < arr.length; j++) {
      //       {
      //         temp.push(arr.slice(i, j + 1))
      //       }
      //     }
      //   }
      //   let len = 0
      //   let t = []
      //   let result = temp.reduce((e, v, index) => {
      //     if (v.join('') === v.reverse().join('')) {
      //       t.push(v)
      //       len = Math.max(len, v.length)
      //       return {
      //         len,
      //         t,
      //       }
      //     }
      //   })
      //   let re = result.t.find((e) => {
      //     if (e.length == result.len) {
      //       return e
      //     }
      //   })
      //   return re.join('')
      // }
      // 中心扩散法：思路：分最长回文子串是奇数和偶数的情况，定义start为最长回文子串开始的索引，然后循环字符串，不断不断向外扩展回文字符串的长度，
      // 循环的过程中更新最大回文子串的长度和start的位置，最后返回start到start+ maxLength的子串就是本题的答案（即只要存在回文子串，最小的必然是偶数个aa类型或者奇数个aba类型的，然后再向外扩展）
      // var longestPalindrome = function (s) {
      //   if (s.length <= 0) {
      //     //边界条件
      //     return s
      //   }
      //   let start = 0 //最长回文子串开始的索引
      //   let maxLength = 1 //初始化最大回文子串长度
      //   function h(left, right) {
      //     //当s[left]，和 s[right]相等时，不断向外扩展回文字符串的长度 例如 babad中, bab  b==b
      //     while (left >= 0 && right < s.length && s[left] === s[right]) {
      //       // 找到最小两边都相等的回文串开始向外各自扩展一位
      //       if (right - left + 1 > maxLength) {
      //       //每次更新最大长度，防止其他短长度的回文串进来
      //         // 这部操作是为了获取下标用来截取字符串  right - left + 1就是相等两边的长度
      //         maxLength = right - left + 1 //更新最大回文子串的长度
      //         start = left //更新start的位置
      //       }
      //       left--
      //       right++
      //     }
      //   }
      //   for (let i = 0; i < s.length; i++) {
      //     // 循环找到最中间的奇数个或者偶数个最小回文字符串，在向外扩展
      //     h(i - 1, i + 1) //回文子串是奇数
      //     h(i, i + 1) //回文子串是偶数
      //   }
      //   return s.substring(start, start + maxLength)
      // }

      // NO.5  复杂链表的复制
      // 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
      /**
       * // Definition for a Node.
       * function Node(val, next, random) {
       *    this.val = val;
       *    this.next = next;
       *    this.random = random;
       * };
       */
      /**
       * @param {Node} head
       * @return {Node}
       */
      // function Node(val, next, random) {
      //   this.val = val
      //   this.next = next
      //   this.random = random
      // }
      // let head = {
      //   val: 7,
      //   random: null,
      //   next: {
      //     val: 13,
      //     random: 0,
      //     next: {
      //       val: 11,
      //       random: 4,
      //       next: null,
      //     },
      //   },
      // }

      // var copyRandomList = function (head) {
      //   let map = new Map()

      //   function copy(node) {
      //     if (!node) return node
      //     console.log(node, 'node')
      //     if (map.has(node)) return map.get(node)

      //     let res = new Node()
      //     map.set(node, res)
      //     res.val = node.val
      //     res.next = copy(node.next)
      //     res.random = copy(node.random)
      //     return res
      //   }
      //   return copy(head)
      // }
      // console.log(copyRandomList(head), 'hr')

      // ****************************** *************************************************************************************************************************
      // NO.6 二维数组中的查找
      // 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
      // 请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

      // 示例:
      // 现有矩阵 matrix 如下：
      // [
      //   [1,   4,  7, 11, 15],
      //   [2,   5,  8, 12, 19],
      //   [3,   6,  9, 16, 22],
      //   [10, 13, 14, 17, 24],
      //   [18, 21, 23, 26, 30]
      // ]
      // 给定 target = 5，返回 true。
      // 给定 target = 20，返回 false。

      /**
       * @param {number[][]} matrix
       * @param {number} target
       * @return {boolean}
       */
      // 根据题意已知，二维数组从左往右递增，从上往下递增，所以得出以下结论：
      // 某列的某个数字，该数之上的数字，都比其小；
      // 某行的某个数字，该数右侧的数字，都比其大；
      // 所以，解题流程如下所示：
      // 以二维数组左下角为原点，建立直角坐标轴。
      // 若当前数字大于了查找数，查找往上移一位。
      // 若当前数字小于了查找数，查找往右移一位。

      //   var findNumberIn2DArray = function (matrix, target) {
      //     if (!matrix.length) return false
      //     let x = matrix.length - 1,
      //       y = 0
      //     while (x >= 0 && y < matrix[0].length) {
      //       if (matrix[x][y] === target) {
      //         return true
      //       } else if (matrix[x][y] > target) {
      //         x--
      //       } else {
      //         y++
      //       }
      //     }
      //     return false
      //   }

      // findNumberIn2DArray(
      //   [
      //     [1, 4, 7, 11, 15],
      //     [2, 5, 8, 12, 19],
      //     [3, 6, 9, 16, 22],
      //     [10, 13, 14, 17, 24],
      //     [18, 21, 23, 26, 30],
      //   ],
      //   5
      // )

      // NO.7 树的子结构
      // 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)=
      // B是A的子结构， 即 A中有出现和B相同的结构和节点值。
      // 例如:
      // 给定的树 A:
      //      3
      //     / \
      //    4   5
      //   / \
      //  1   2
      // 给定的树 B：
      //    4
      //   /
      //  1
      // 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
      // 示例 1：

      // 输入：A = [1,2,3], B = [3,1]
      // 输出：false
      // 示例 2：

      // 输入：A = [3,4,5,1,2], B = [4,1]
      // 输出：true
      let A = {
        val: 3,
        left: {
          val: 4,
          left: {
            val: 1,
            left: null,
            right: null,
          },
          right: {
            val: 2,
            left: null,
            right: null,
          },
        },
        right: {
          val: 5,
          left: null,
          right: null,
        },
      }
      let B = {
        val: 4,
        left: {
          val: 1,
          left: null,
          right: null,
        },
        right: null,
      }
      //     function isSubStructure(root1, root2) {
      //     let result = false;
      //     //当root1和root2都不为null的时候，才进行比较。否则直接返回false
      //     if (root1 != null && root2 != null) {
      //         //如果找到了对应root2的根节点的点
      //         if (root1.val == root2.val) {
      //             //以这个根节点为为起点判断是否包含root2
      //             result = isSame(root1, root2);
      //         }
      //         if (!result) {
      //             //如果找不到，那么就再去root1的左儿子当作起点，去判断时候包含root2
      //             result = isSubStructure(root1.left, root2);
      //         }
      //         if (!result) {
      //             //如果还找不到，那么就再去root1的右儿子当作起点，去判断时候包含root2
      //             result = isSubStructure(root1.right, root2);
      //         }
      //     }
      //     return result;
      // }

      // function isSame(node1, node2) {
      //     //如果node2是空的，返回true
      //     if (node2 == null) {
      //         return true;
      //     }
      //     //如果node1非空，返回false
      //     if (node1 == null) {
      //         return false;
      //     }
      //     //如果其中有一个点没有对应上，返回false
      //     if (node1.val != node2.val) {
      //         return false;
      //     }
      //     //如果根节点对应的上，那么就分别去子节点里面匹配
      //     return (
      //         isSame(node1.left, node2.left) &&
      //         isSame(node1.right, node2.right)
      //     );
      // }
    </script>
  </body>
</html>
